def Lz77Uncompress(source,target):
    fp=open(source,'rb')
    if fp.read(1)!='\x10':
        print 'this file is not lz77 compress'
    UnCompressSize=ord(fp.read(1))+ord(fp.read(1))*0x100+ord(fp.read(1))*0x10000
    
    string=''
    while True:
        if len(string)>=UnCompressSize:
            break
        ctrlnum=ord(fp.read(1))
        for i in xrange(8):
            bit=(ctrlnum>>(7-i))%2
            if bit==0:
                string+=fp.read(1)
            else:
                byte=fp.read(1)
                length=(ord(byte)/0x10)+3
                byte2=fp.read(1)
                windows=(ord(byte)%0x10)*0x100+ord(byte2)+1
                for j in xrange(length):
                    string+=string[-windows:-windows+1]
    fp.close()
    
    tar=open(target,'wb')
    tar.write(string)
    tar.close()

def Lz77exUncompress(source,target):
    fp=open(source,'rb')
    if fp.read(1)!='\x11':
        print 'this file is not lz77ex compress'
    UnCompressSize=ord(fp.read(1))+ord(fp.read(1))*0x100+ord(fp.read(1))*0x10000
    
    string=''
    while True:
        print 'offset=%08x'%fp.tell()
        print 'length=%08x'%len(string)
        if fp.tell()==0xa1cb:
            break
        if len(string)>=UnCompressSize:
            break
        ctrlnum=ord(fp.read(1))
        for i in xrange(8):
            bit=(ctrlnum>>(7-i))%2
            if bit==0:
                string+=fp.read(1)
            else:
                byte=fp.read(1)
                length=(ord(byte)/0x10)+1
                byte2=fp.read(1)
                windows=(ord(byte)%0x10)*0x100+ord(byte2)+1
                for j in xrange(length):
                    string+=string[-windows:-windows+1]
    fp.close()
    
    tar=open(target,'wb')
    tar.write(string)
    tar.close()

Lz77exUncompress('ui12_bg00.lz77Ex','ui12_bg00.lz77Ex.bin')